package 剑指offer.demo5;

import java.util.ArrayList;

//https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?
/*
array存放处理好的正确列表，list这是一个一个进行判断的过程，如果满足题目条件就
 */
public class 二叉树中和为某一值的路径_2 {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        //定义新的返回列表和存储列表
        ArrayList<ArrayList<Integer>> array = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        //调用方法进行处理
        fun(root , expectNumber , array , list);
        //返回
        return array;
    }

    //给定二叉树、需求值、带返回列表、存储列表，进行列表操作
    public void fun(TreeNode root , int num , ArrayList<ArrayList<Integer>> result , ArrayList<Integer> list){
        if (root == null){
            return;
        }
        //把当前值加入list
        list.add(root.val);
        //num数值相应变化
        num -= root.val;
        //左右都空且数值减到0时说明所有条件满足，把列表加进去
        if (root.left == null && root.right == null && num == 0){
            //注意这里result内部保存值是以list形式存在，所以我们要重新传一个值把list放进去
            result.add(new ArrayList(list));
        }
        //要么有左右孩子分别处理，要不最后列表走到头了，还是不满足条件，把最后一个值删掉，因为此时可能在递归返回过程中，所以只删一个继续处理
        fun(root.left , num , result , list);
        fun(root.right , num , result , list);
        list.remove(list.size() - 1);
    }

    //题目给定二叉树
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }
}
